package java_1_13.delete;
/**
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
 * LeetCode82号问题
 * 创建虚拟头节点-问题简单化
 */
public class Delete {
    private int size;
    public ListNode head;
    public ListNode delete(){
        ListNode dummyHead=new ListNode(-101);
        dummyHead.next=head;
        ListNode prev=dummyHead;
        ListNode node=dummyHead.next;
        while(node!=null){
            ListNode next=node.next;//next的后移操作
            if(next==null){//链表只有一个节点
                return dummyHead.next;
            }else{//链表至少有两个结点
                if(node.val== next.val){
                    //此时next持续后移继续扫描重复元素
                    while(next!=null&&next.val==node.val){
                        next=next.next;
                    }
                    //走到这里next!=node,此时prev直接指向next（但prev不更新，只有prev node next都不同才更新prev ）跳过重复节点
                    //node更新到next位置，next去node的下一位
                    prev.next=next;
                    node=next;
                }else{//node next值不等，三者才同时后移
                    prev=prev.next;
                    node=node.next;
                    //next的后移操作进程序就有
                }
            }
        }
        head=dummyHead.next;//把头节点更新一下
        return dummyHead.next;
    }
    public void addFirst(int val){
        ListNode node=new ListNode(val);
        //判断火车头是否为空
        if(head==null){
            head=node;
        }else{//火车有车厢，把新车厢挂载到火车头部
            node.next=head;
            head=node;
        }
        size++;
    }
    public String toString(){
        String ret="";
        ListNode node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }
}

 class ListNode {
    int val;
     ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
              ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }